"""
桶排序适用于分布均匀的数据，通过将数据分到有限数量的桶中，再对每个桶内数据进行排序（通常用插入排序），最后合并所有桶的结果。
桶排序：
适用于浮点数或分布均匀的整数
时间复杂度取决于桶内排序算法（平均 O (n)，最坏 O (n²)）
需要额外空间存储桶
"""
def bucket_sort(arr):
    """
    桶排序实现

    参数:
        arr: 待排序的列表（假设为非负浮点数，范围在[0, 1)之间）
    返回:
        排序后的列表
    """
    if not arr:  # 处理空列表
        return arr

    # 1. 创建空桶（这里根据数据范围创建10个桶）
    num_buckets = len(arr)  # 桶的数量通常与数据量相同或为固定值
    buckets = [[] for _ in range(num_buckets)]

    # 2. 将元素分配到对应的桶中
    for num in arr:
        # 计算元素应放入的桶索引（假设数据在[0,1)，放大后取整数部分）
        bucket_index = int(num * num_buckets)
        # 防止索引越界（例如num=1.0时）
        if bucket_index == num_buckets:
            bucket_index -= 1
        buckets[bucket_index].append(num)

    # 3. 对每个桶内的元素进行排序（这里使用内置排序，也可替换为插入排序）
    for bucket in buckets:
        bucket.sort()  # 桶内排序

    # 4. 合并所有桶的结果
    sorted_arr = []
    for bucket in buckets:
        sorted_arr.extend(bucket)  # 将每个桶的元素依次加入结果

    return sorted_arr


# 测试桶排序
if __name__ == "__main__":
    test_arr = [0.42, 0.32, 0.33, 0.52, 0.37, 0.47, 0.51]
    print("桶排序前:", test_arr)
    print("桶排序后:", bucket_sort(test_arr))